In this chapter we want to show a model of two-dimensional automata based on
Wang tiles. This model is called $\mu$-directed Wang automaton, abbreviated as
$\mu$-WA and was introduced in 2010 by V. Lonati and M. Pradella
in~\cite{lonati2010picture}. This automaton uses a scanning strategy to scan an
input picture. In each computation step, the automaton colors the edges it
visits. After each computation, the automaton can accept the input picture if
the label of the produced Wang picture is equal to the input picture. The
original definition of a $\mu$-directed Wang automaton uses a blind scanning
strategy. Here we use the formal definition of~\cite{lonati2011towards} that
uses a polite scanning strategy and is non-deterministic abbreviated with
$\mu$-NWA.
\begin{definition}
A \emph{$\mu$-directed nondeterministic Wang automaton} is a 5-tuple \\
$M = (\Sigma, C, \delta, \mu, F)$, where 
\begin{compactitem}
	\item $\Sigma$ is a finite input alphabet,
	\item C is a finite set of colors,
	\item $\delta: \Sigma_C \times Dirs \rightarrow 2^{\Sigma_{4C}}$ is a partial
	function such that for each tile in $\delta(A, d)$ extends $A$. That means if
	$A$ is a partial Wang tile $\delta$ fills in the missing colors.
	\item $\mu = (\eta, c_s, d_s)$ is a polite scanning strategy such that for
	tiles $A$ and directions $d$ with $\delta(A, d) \neq \emptyset$ implies
	$\eta(\Delta_A, d) \neq \perp$ and
	\item $F \subset \Sigma_{4C}$ is the set of final tiles.
\end{compactitem}
\end{definition}
A $\mu$-WA is deterministic if $\delta(A, d)$ has at most one element for every
tile $A$ and direction $d$. Deterministic $mu$-WA's are abbreviated as
$\mu$-DWA.
The union of all $\familyOf{$\mu$-DWA}$ for all polite scanning strategies $\mu$
is denoted with Scan-DREC. Remark that the class $Snake$-DREC can also be
defined by the closure under rotation of $\familyOf{$\mathcal{S}$-DWA}$.
\begin{example}
In~\cite{anselmo2007recognizable} it was shown that the language $L_{fr =
r'}$ is in $t2b$-UREC and in $l2r$-UREC. It was proved that $d$-UREC coincides
with $\familyOf{$\mathcal{S}^{d}$-DWA}$~\cite{lonati2010deterministic} hence the
corresponding $\mathcal{S}^{t2b}$-DWA and $\mathcal{S}^{l2r}$-DWA can be built.
They basically produce the tiling of 
\begin{center}
\begin{tabular}{|E{0.22cm}|E{0.22cm}|E{0.22cm}|E{0.22cm}|E{0.22cm}|}
\hline
a & b & a & a & b \tabularnewline
\hline
b & a & b & a & a \tabularnewline
\hline
a & a & b & a & b \tabularnewline
\hline
a & b & a & a & b \tabularnewline
\hline
a & b & a & b & b \tabularnewline
\hline
\end{tabular}
\hfill
\begin{tabular}{|D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}D{0.5cm}|}
\hline
   & \#        &          & \#        &          & \#        &          & \#        &          & \#        &    \tabularnewline 
\# & \boxed{a} & $\circ$  & \boxed{b} & $\circ$  & \boxed{a} & $\circ$  & \boxed{a} & $\circ$  & \boxed{b} & \# \tabularnewline
   & a         &          & b         &          & a         &          & a         &          & b         &    \tabularnewline
\# & \boxed{b} & $\times$ & \boxed{a} & $\times$ & \boxed{b} & $\times$ & \boxed{a} & $\times$ & \boxed{a} & \# \tabularnewline
   & a         &          & b         &          & a         &          & a         &          & b         &    \tabularnewline
\# & \boxed{a} & $\circ$  & \boxed{a} & $\times$ & \boxed{b} & $\times$ & \boxed{a} & $\times$ & \boxed{b} & \# \tabularnewline
   & a         &          & b         &          & a         &          & a         &          & b         &    \tabularnewline
\# & \boxed{a} & $\circ$  & \boxed{b} & $\circ$  & \boxed{a} & $\circ$  & \boxed{a} & $\circ$  & \boxed{b} & \# \tabularnewline
   & a         &          & b         &          & a         &          & a         &          & b'        &    \tabularnewline
\# & \boxed{a} & $\circ$  & \boxed{b} & $\circ$  & \boxed{a} & $\times$ & \boxed{b} & $\times$ & \boxed{b} & \# \tabularnewline
   & \#        &          & \#        &          & \#        &          & \#        &          & \#        &    \tabularnewline
\hline
\end{tabular}
\end{center}
except for a delay of one
row in case of $\mathcal{S}^{t2b}$-DWA, and one column in case of
$\mathcal{S}^{l2r}$-DWA.
\label{example_mu_directed_wang_automaton}
\end{example}
Now let us regard the closure properties and class hierarchy.
\begin{theorem}
For any polite $\mu$, $\familyOf{$\mu$-DWA}$ is closed under union, intersection
and complement.
\end{theorem}
This is proved in~\cite{lonati2010deterministic}. There it is shown that
$\familyOf{$\mu$-DWA}$ is closed under intersection and complement which
implies the closure under union.

The following theorem is a consequence of the previous theorem and the
definition of $Scan$-DREC.
\begin{theorem}
$Scan$-DREC is closed under complement, rotation and mirroring.
\end{theorem}
We now want to show the language hierarchy. The following theorems
are all proved by V. Lonati and M. Pradella in~\cite{lonati2010deterministic}.
\begin{theorem}
For every polite scanning strategy $\mu$, $\familyOf{$\mu$-WA} =$ REC holds.
\label{wa_=_rec}
\end{theorem}
In the proof of this theorem it was shown that for every polite scanning
strategy $\mu$, the $\mu$-directed Wang automata are equivalent to Wang systems.

The following theorem is a consequence of the previous theorem.
\begin{theorem}
For every polite scanning strategy $\mu$, $\familyOf{$\mu$-DWA} \subseteq$ REC.
\end{theorem}
\begin{theorem}
$Scan$-DREC $\subset$ REC.
\end{theorem}
Because REC is not closed under complement and with Theorem~\ref{wa_=_rec} the
above theorem followed.
\begin{theorem}
$\familyOf{$\mathcal{S}$-DWA}$ and $\familyOf{$\mathcal{C}$-DWA}$ are
incomparable.
\end{theorem}
$L_{half}$ is the language of all picture $p$ with $l_1(p) \geq l_2(p) \geq 4$
and with the first row of the form $w\bar{w}$, where $\bar{w}$ is the reverse of
$w$. It was proved that the intersection of $L_{half}$ with its $180$ degree
rotation is an element of $\familyOf{$\mathcal{C}$-DWA} \setminus
\familyOf{$\mathcal{S}$-DWA}$. On the other hand is $L_{fr = r'} \in
\familyOf{$\mathcal{S}$-DWA} \setminus \familyOf{$\mathcal{C}$-DWA}$, where
$L_{fr = r'}$ is the language described in Section~\ref{urec}.
\begin{theorem}
$Snake$-DREC $\subset$ $Scan$-DREC $\subseteq$ UREC.
\end{theorem}
By definition it follows $Snake$-DREC $\subseteq$ $Scan$-DREC $\subseteq$ UREC.
It was shown that the language $L$, which is the intersection of all $90$
degree rotations of the language $L_{half}$, is an element of $Scan$-DREC
$\setminus$ $Snake$-DREC, which implies the proper subset from $Snake$-DREC and
$Scan$-DREC.
\begin{theorem}
$\familyOf{$\mathcal{S}^d$-DWA}$ = $d$-UREC, $d \in \{t2b, bt2, l2r, r2l\}$.
\end{theorem}
To show that $\familyOf{$\mathcal{S}^d$-DWA}$ $\subseteq$ $d$-UREC
the construction of Theorem~\ref{wa_=_rec} was used. For the other direction it was build
a $\mathcal{S}^{t2b}$-DWA that simulates a given $t2b$-UTS. The theorem follows
by applying rotations. 

Further results on this automaton can be found in~\cite{LonatiPradella2011}
and~\cite{lonati2010deterministic}.
\label{scan_drec}